//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 
//
// candidates 中的每个数字在每个组合中只能使用一次。 
//
// 注意：解集不能包含重复的组合。 
//
// 
//
// 示例 1: 
//
// 
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//输出:
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//] 
//
// 示例 2: 
//
// 
//输入: candidates = [2,5,2,1,2], target = 5,
//输出:
//[
//[1,2,2],
//[5]
//] 
//
// 
//
// 提示: 
//
// 
// 1 <= candidates.length <= 100 
// 1 <= candidates[i] <= 50 
// 1 <= target <= 30 
// 
// Related Topics 数组 回溯 
// 👍 749 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSumIi {
    public static void main(String[] args) {
        Solution solution = new CombinationSumIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 两个剪枝的操作，一个是避免重复，一个是目标值太小
     * 避免重复的操作是使用一个visited数组，和之前的一道题目一样，如果当前值==前值且前值为false则跳过当前值
     * dfs仍然传入的是起始下标以及目标剩余值
     * 另一个剪枝是提前break，避免多余判断
     *
     * 避免重复时的另一种剪枝方法
     * 这个是避免同一层取到相同的元素，但是在不同层可以取到相同的元素
     * 比如 1 1  target=2 当begin = 0 时 添加第一个元素的for循环中只能取到第一个1
     * 但是到达添加第二个元素的for训话时，begin = 1 取第二个1的时候i也等于1，所以可以进行添加
     * 只有当i==begin的时候相同元素才能添加，因为已经是不同层了
     * if(i>begin && candidates[i] == candidates[i-1]) continue;
     */
    class Solution {
        List<List<Integer>> res;
        List<Integer> temp;
        int[] candidates;
        int len;
        boolean[] visited;
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);//仍然是先进行了排序
            len = candidates.length;
            this.candidates = candidates;
            res = new ArrayList<>();
            temp = new ArrayList<>();
            visited = new boolean[len];
            dfs(target,0);
            return res;
        }

        private void dfs(int target, int begin) {
            if (target == 0){
                res.add(new ArrayList<>(temp));//可以添加了
            }else {
                for (int i = begin; i <len ; i++) {
                    if (target < candidates[i]) break;//提前剪枝
                    //这里是避免拿到重复的值，和之前分析的一样，visited[i-1]为true时说明是同一枝，可以用
                    //if (i!=0&&candidates[i] == candidates[i-1]&&!visited[i-1]) continue;
                    if(i>begin && candidates[i] == candidates[i-1]) continue;// TODO 这种剪枝方式太秀了
                    visited[i] = true;
                    temp.add(candidates[i]);
                    dfs(target-candidates[i],i+1);//这里传入下一个位置，因为排序过了
                    temp.remove(temp.size()-1);
                    visited[i] = false;//恢复访问状态为false，所以同一层如果前一个为false则说明已经访问了
                }
            }
        }

        /**
         * 二刷，这道题目的难点就在于剪枝，做的时候倒是很快就想起来剪枝了
         */
        public void dfs(int index, int target, int[] candidates, List<Integer> path){
            if (target == 0) res.add(new ArrayList(path));
            else{
                for (int i = index; i < candidates.length; i++){
                    if ( target - candidates[i] < 0) break;
                    //TODO 这里非常重要，去重的方法
                    if(i!=index && candidates[i] == candidates[i-1]) continue;
                    path.add(candidates[i]);
                    dfs(i+1, target - candidates[i], candidates, path);
                    path.remove(path.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}